package question.solution31;

import question.SolutionTemplate;

public class Solution31 implements SolutionTemplate {

    public void nextPermutation(int[] nums) {
        // 9 8 7 6 5 3 4 2 1 ==>  9 8 7 6 5 4 1 2 3
        // 9 8 7 6 5 2 4 3 1 ==>  9 8 7 6 5 3 1 2 4
        // 9 8 7 6 5 2 4 3 3 1 ==>  9 8 7 6 5 3 1 2 3 4
        if(nums.length <=1){
            return;
        }
        int changeIndex = -1;
        for(int i=nums.length-1;i>0;i--){
            if(nums[i] > nums[i-1]){
                changeIndex = i-1;
                break;
            }
        }
        if(changeIndex == -1){
            swapNums(nums, 0, nums.length-1);
            return;
        }
        int swapIndex = getIndexOfFirstBiggerNumber(nums, changeIndex);
        int temp = nums[changeIndex];
        nums[changeIndex] = nums[swapIndex];
        nums[swapIndex] = temp;
        swapNums(nums, changeIndex+1, nums.length-1);

    }

    private int getIndexOfFirstBiggerNumber(int[] nums, int indexToCompare){
        for(int i=nums.length-1;i > indexToCompare;i--){
            if(nums[i] > nums[indexToCompare]){
                return i;
            }
        }
        return -1;
    }

    private void swapNums(int[] nums, int startIndex, int endIndex){
        while(startIndex < endIndex){
            int temp = nums[startIndex];
            nums[startIndex] = nums[endIndex];
            nums[endIndex] = temp;
            startIndex++;
            endIndex--;
        }
    }

    public void test() {
        int[] fuck = {5,6,5,4,4,6,9,5,8,0,3,2};
        nextPermutation(fuck);

        return;
    }
}
